package 剑指offer.数组;

/**
 * 给出一个被翻转过的数组：[3,4,5,1,2]，求出他的最小值
 * <p>
 * 解法一：暴力循环
 * 解法二：二分法查找
 */
public class 第11题旋转数组的最小数字 {

    /*
    二分法查找：设定头尾指针，同时比较他们的值和中间元素的大小
    然后移动头尾指针往中间走，从而快速确定答案

    考虑以下特殊情况：
    1. 数组并没有翻转就是有序的：[1,2,3,4,5]，答案就是第一个元素
    2. 数组里面包含重复元素，无法确定头尾指针和中间值的大小关系：[1,0,1,  1,1]，只能顺序遍历数组了
     */
    public static int findMin(int[] nums) {
        int headIndex = 0;
        int tailIndex = nums.length - 1;
        // middle 将数组分为两个区间 [head, middle]、[middle, tail]
        int middle = 0;

        if (nums[headIndex] < nums[tailIndex]) {
            return nums[headIndex];
        }

        while (nums[headIndex] >= nums[tailIndex]) {
            // 两指针重合，找到最小值就是 tail 指向的数字
            if (tailIndex - headIndex == 1) {
                //middle = tailIndex;
                break;
            }
            middle = (headIndex + tailIndex) / 2;
            if (nums[headIndex] == nums[tailIndex] && nums[headIndex] == nums[middle]) {
                int min = nums[0];
                for (int i = 1; i < nums.length - 1; i++) {
                    if (nums[i] < min) {
                        min = nums[i];
                    }
                }
                return min;
            }
            // middle 指向的值大于头指针，说明 middle 在前面的升序数组里面，head 指针要往后收缩
            if (nums[middle] >= nums[headIndex]) {
                headIndex = middle;
            }
            // middle 指向的值小于尾指针说明 middle 在后面的升序数组里面，tail 指针要往前收缩
            if (nums[middle] <= nums[tailIndex]) {
                tailIndex = middle;
            }

        }
        //
        return nums[tailIndex];
    }

    public static void main(String[] args) {
//        int[] nums = {3, 4, 5, 1, 2,};
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println(findMin(nums));
    }
}
